#include<vector>
using namespace std;
class NumArray {
private:
    int n = 0;
    vector<int> tree;
public:
    NumArray(vector<int>& nums):n(nums.size()),tree(2* n){
        for (int i = n; i < 2 * n; ++i)
            tree[i] = nums[i - n];
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    void update(int i, int val) {
        int index = i + n;
        tree[index] = val;
        while (index > 0) {
            int left = index;
            int right = index;
            if (index % 2 == 1)
                --left;
            else
                ++right;
            tree[index / 2] = tree[left] + tree[right];
            index /= 2;
        }
    }

    int sumRange(int i, int j) {
        int left = i + n, right = j + n;
        int sum = 0;
        while (left <= right) {
            if (left % 2 == 1)
                sum += tree[left++];
            if (right % 2 == 0)
                sum += tree[right--];
            left /= 2;
            right /= 2;
        }
        return sum;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */